package com.banmao.CarlCamp.Day04;

import java.util.HashSet;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
 */
public class LC07_2 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 相交链表的特性 —— 从相交点开始，两条链表的尾长是一样的
        // 思路：求出两个链表的长度，将两个指针指向最短链表的起点以及更长链表的尾长与短链表相等的节点
        // （求出两个链表长度的差值，然后让curA移动到，和curB末尾对齐的位置）
        // 同步遍历，找到两个相同的节点，即两个链表的相交点

        // 求两个链表的长度
        int lenA = 0, lenB = 0;
        ListNode cur = headA;
        while (cur != null) {
            lenA++;
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            lenB++;
            cur = cur.next;
        }

        ListNode longList = null, shortList = null;
        int longLen = 0, shortLen = 0;
        if (lenA > lenB) {
            longList = headA;
            shortList = headB;
            longLen = lenA;
            shortLen = lenB;
        } else {
            longList = headB;
            shortList = headA;
            longLen = lenB;
            shortLen = lenA;
        }

        // 两条链表长度之差
        int gap = longLen - shortLen;
        // 将长链表指针移动到第 gap 个节点
        while (gap > 0) {
            longList = longList.next;
            gap--;
        }

        // 同步遍历，指针相同则返回
        while (longList != null && shortList != null) {
            if (longList == shortList) {
                return longList;
            }
            longList = longList.next;
            shortList = shortList.next;
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
